#include <iostream>
#include <vector>

/*
堆排序的核心思想：

将待排序序列构造成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换，此时末尾元素就为最大值
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

*/

// i: 当前节点坐标index
// 做一次heapify，只会把父节点和字节点中的最大值，赋值给父节点, 再下面的字节点没有传递给父节点。
 void maxHeapify(std::vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1; //左孩子坐标
        int r = i * 2 + 2; //右孩子坐标
        int largest = i;
        if (l < heapSize && a[l] > a[largest]) { //坐标不可能=headsize（节点数）
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            std::swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
}

void buildMaxHeap(std::vector<int>& a, int heapSize) {
    /*
      父节点是（i-1）/ 2
      子节点： 2*i + 1， 2*i + 2

      int last_node = heapSize - 1;
      int parent_node = (last_node - 1) / 2;
      for(int i = parent_node; i >=0 ; --i)
          maxHeapify(a, i, heapSize);

    */
        for (int i = heapSize / 2; i >= 0; --i) { //从最底层依次开始做heapify
            maxHeapify(a, i, heapSize);
        } 
}

void heap_sort(std::vector<int>& a, int heapSize)
{
    buildMaxHeap(a, heapSize);  //根结点最大，依次与尾节点交换
   
    for(int i = heapSize - 1;i >= 0; i--) 
    { 
        std::swap(a[i], a[0]); // 依次取堆顶元素，交换之后堆顶元素是’最后‘一个元素，已经不是最大值了
        maxHeapify(a, 0, i); //i递减就代表了节点的个数;  第二个参数0表示从堆顶heapify,依次选取新的对顶
    }
}

int main()
{
     std::vector<int> ve{2, 5, 3, 1, 10, 4};
     //buildMaxHeap(ve, ve.size());
     heap_sort(ve, ve.size());

     for(auto& value : ve)
     {
        std::cout << value << std::endl;
     }

}

/*
1
2
3
4
5
10
*/
